package demo01Array;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName $ {NAME}
 * @Description TODO
 * @Author shenxinyuan
 * @Date $ {DATE} $ {TIME}
 * @Version 1. 0
 **/

public class OddFirstAndEvenLast {

    int[] arr = {1, 2, 3, 4, 5, 6};

    /**
     * @Author shenxinyuan
     * @Description //TODO
     * @Date 13:57 2021/7/17
     * @Param [array]
     * @return int[]
     **/
    public int[] reOrderArray (int[] array) {
        // write code here
        if(array.length == 0){
            return array;
        }
        Queue<Integer> jishu = new LinkedList<>();
        Queue<Integer> oushu = new LinkedList<>();
        for(int i = 0;i < array.length ;i++){
            if(array[i] % 2 != 0){
                jishu.add(array[i]);
            }else{
                oushu.add(array[i]);
            }
        }
        for(int i = 0;i < array.length ;i++){
            if(!jishu.isEmpty()){
                array[i] = jishu.poll();
            }else{
                array[i] = oushu.poll();
            }
        }
        return array;
    }

    public int[] reOrderArrayOptimized (int[] array) {
        // write code here
        //双指针，头尾指针
        int[] nums = new int[array.length];
        int head = 0;
        int tail = array.length-1;
        int index_head = head;
        int index_tail = tail;
        while(head < array.length && tail >= 0){
            if(array[head] % 2 == 1){
                //奇数，放前面
                nums[index_head] = array[head];
                index_head++;
            }
            head++;
            if(array[tail] % 2 == 0){
                //从后到前，如果为偶数，则从后开始填
                nums[index_tail] = array[tail];
                index_tail--;
            }
            tail--;
        }
        return nums;
    }
    @Test
    public void test() {
        System.out.println("reOrderArray(arr) = " + Arrays.toString(reOrderArray(arr)));
    }
}
